#ifndef LIST_TABLE_H
#define LIST_TABLE_H

#include "list_node.h"

template <typename _Type>
class ListTable
{
public:
    class _List_iterator;
    class _vector;
    typedef _List_iterator iterator;
    typedef _vector vector;
    class ListItem : public ListNode
    {
    public:
        ListItem() {}
        ListItem(const _Type &i)
            : ListNode(), _M_data(i)
        {}

        _Type _M_data;
    };
    class _List_iterator
    {
    public:
        typedef _List_iterator _Self;
        typedef _Type          value_type;
        typedef _Type*         pointer;
        typedef _Type&         reference;

        _List_iterator()
            : _M_node(0) {}
        _List_iterator(ListItem *n)
            : _M_node(n) {}

        reference operator*() const
        {
            return _M_node->_M_data;
        }

        pointer operator->() const
        {
            return &(_M_node->_M_data);
        }

        _Self& operator++()
        {
            _M_node = static_cast<ListItem *>(_M_node->getFirst());
            return *this;
        }

        _Self operator++(int)
        {
            _Self __tmp = *this;
            _M_node = static_cast<ListItem *>(_M_node->getFirst());
            return __tmp;
        }

        _Self& operator--()
        {
            _M_node = static_cast<ListItem *>(_M_node->getLast());
            return *this;
        }

        _Self operator--(int)
        {
            _Self __tmp = *this;
            _M_node = static_cast<ListItem *>(_M_node->getLast());
            return __tmp;
        }

        bool operator==(const _Self& __x) const
        {
            return _M_node == __x._M_node;
        }

        bool operator!=(const _Self& __x) const
        {
            return _M_node != __x._M_node;
        }


        ListItem *_M_node;
    };

    class _vector
    {
        _vector(_vector &);
        _vector &operator =(_vector &);
    public:
        typedef _Type*  type_ptr;
        typedef _Type  type_node;
        _vector()
            : mArray(nullptr), counts(0), ref(0)
        {}
        ~_vector()
        {
            delete [] mArray;
        }

        type_node &operator [] (int i)
        {
            return *(mArray[i]);
        }
        type_node &operator [] (int i) const
        {
            return *(mArray[i]);
        }

        void push_back(type_node *node)
        {
            if (ref == counts)
            {
                reallocVector();
            }

            mArray[ref++] = node;
        }

        int  size() const
        {
            return ref;
        }


        void clear()
        {
            ref = 0;
        }

        bool empty() const
        {
            return 0 == ref;
        }

    private:
        void reallocVector()
        {
            counts += 20;

            type_ptr *arr = new type_ptr[counts];

            if (mArray)
            {
                for (int i = 0; i < ref; ++i)
                {
                    arr[i] = mArray[i];
                }
            }
            mArray = arr;
        }

        type_ptr   *mArray;
        int         counts;
        int         ref;
    };

    ListTable()
    {
    }
    ~ListTable()
    {
        clear();
    }

    void push_back(const _Type &it)
    {
        mRoot.add(new ListItem(it));
    }
    void push_front(const _Type &it)
    {
        mRoot.addFirst(new ListItem(it));
    }
    void push_back(iterator &it)
    {
        mRoot.add(it._M_node);
    }
    void push_front(iterator &it)
    {
        mRoot.addFirst(it._M_node);
    }
    iterator insert(iterator pos, const _Type &it)
    {
        ListItem *_tmp = new ListItem(it);
        pos._M_node->addFirst(_tmp);

        return iterator(_tmp);
    }

    //!  把当前it指向的数据，移动到list队列中
    static void move(iterator it, ListTable &list)
    {
        it._M_node->del();
        list.push_back(it);
    }
    void move(iterator it)
    {
        it._M_node->del();
        this->push_back(it);
    }

    // 默认是升序排列（小的在第一个，大的在最后），数据需要重载小于(<)运算符
    void sort()
    {
        //使用归并排序
        mergeSort(&mRoot);        
    }
    void merge(ListTable &list)
    {
        ListTable left;

        swap(left);

        iterator iL = left.begin();
        iterator iR = list.begin();
        for (; iL != left.end() && iR != list.end(); )
        {
            if (*iR < *iL)
            {
                iL._M_node->del();
                push_back(iL);
                iL = left.begin();
            } else
            {
                iR._M_node->del();
                push_back(iR);
                iR = list.begin();
            }
        }

        if (!list.empty())
        {
            for (iR = list.begin(); iR != list.end();)
            {
                iR._M_node->del();
                push_back(iR);
                iR = list.begin();
            }
        }
        if (!left.empty())
        {
            for (iL = left.begin(); iL != left.end();)
            {
                iL._M_node->del();
                push_back(iL);
                iL = left.begin();
            }
        }
    }

    // 默认是降序排列（大的在第一个，小的在最后），数据需要重载小于(<)运算符
    void sort3()
    {
        if (mRoot.next != &mRoot
                && mRoot.next->next != &mRoot)
        {
            ListTable __carry;
            ListTable __tmp[64]; //越界的可能是：list列表数量达到"2^(64-1)"
            ListTable * __fill = &__tmp[0];
            ListTable * __counter;
            do
            {
                __carry.splice(__carry.begin(), *this, begin());

                for(__counter = &__tmp[0];
                    __counter != __fill && !__counter->empty();
                    ++__counter)
                {
                    __counter->merge(__carry);
                    __carry.swap(*__counter);
                }
                __carry.swap(*__counter);
                if (__counter == __fill)
                {
                    ++__fill;
                }
            }
            while ( !empty() );

            for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
            {
                __counter->merge(*(__counter - 1));
            }

            swap( *(__fill - 1) );
        }
    }

    void splice(iterator pos, ListTable &list, iterator i)
    {
        if (list.empty()) return;
        i._M_node->del();
        if (empty())
        {
            pos._M_node->addFirst(i._M_node);
        } else
        {
            pos._M_node->add(i._M_node);
        }
    }

    _Type &back()
    {
        return static_cast<ListItem *>(mRoot.getLast())->_M_data;
    }
    _Type &front()
    {
        return static_cast<ListItem *>(mRoot.getFirst())->_M_data;
    }

    iterator pop_front()
    {
        if (mRoot.isEmpty())
        {
            return end();
        }
        ListItem *node = static_cast<ListItem *>(mRoot.getFirst());

        node->del();

        return iterator(node);
    }
    iterator pop_back()
    {
        if (mRoot.isEmpty())
        {
            return end();
        }
        ListItem *node = static_cast<ListItem *>(mRoot.getLast());

        node->del();

        return iterator(node);
    }

    iterator begin()
    {
        return iterator(static_cast<ListItem *>(mRoot.getFirst()));
    }
    iterator end()
    {
        return iterator(&mRoot);
    }
    void remove(iterator it)
    {
        it._M_node->del();
        delete it._M_node;
    }

    template<typename _del>
    void removeAll(_del del)
    {
        if(del)
        {
            TRAVEL_LIST_AND_DEL(mRoot)
            {
                tmp->del();
                del(static_cast<ListItem *> (tmp)->_M_data);
                delete static_cast<ListItem *> (tmp);
            }
        } else
        {
            clear();
        }
    }

    void clear()
    {
        TRAVEL_LIST_AND_DEL(mRoot)
        {
            tmp->del();
            delete static_cast<ListItem *> (tmp);
        }
    }

    void clearHaveClear()
    {
        TRAVEL_LIST_AND_DEL(mRoot)
        {
            tmp->del();
            static_cast<ListItem *> (tmp)->_M_data.clear();
            delete static_cast<ListItem *> (tmp);
        }
    }

    void genVector(vector &vec)
    {
        vec.clear();

        TRAVEL_LIST_BACK(mRoot)
        {
             vec.push_back(&(static_cast<ListItem *> (tmp)->_M_data));
        }        
    }
    bool empty() const
    {
        return mRoot.isEmpty();
    }
    int size() const
    {
        return mRoot.length();
    }
    void swap(ListTable &l)
    {
        if (empty() && l.empty())
        {
            return;
        }
        if (empty())
        {
            l.mRoot.next->prev = &mRoot;
            l.mRoot.prev->next = &mRoot;
            mRoot.next = l.mRoot.next;
            mRoot.prev = l.mRoot.prev;
            l.mRoot.next = &l.mRoot;
            l.mRoot.prev = &l.mRoot;
        } else if (l.empty())
        {
            mRoot.next->prev = &l.mRoot;
            mRoot.prev->next = &l.mRoot;

            l.mRoot.next = mRoot.next;
            l.mRoot.prev = mRoot.prev;
            mRoot.next = &mRoot;
            mRoot.prev = &mRoot;
        } else
        {
            ListNode tmp;
            tmp.next = mRoot.next;
            tmp.prev = mRoot.prev;
            l.mRoot.next->prev = &mRoot;
            l.mRoot.prev->next = &mRoot;

            mRoot.next->prev = &l.mRoot;
            mRoot.prev->next = &l.mRoot;

            mRoot.next = l.mRoot.next;
            mRoot.prev = l.mRoot.prev;

            l.mRoot.next = tmp.next;
            l.mRoot.prev = tmp.prev;
        }
    }

    ListTable &operator=(const ListTable &l)
    {
        if (l.empty()) return *this;

        mRoot = l.mRoot;
        mRoot.next->prev = &mRoot;
        mRoot.prev->next = &mRoot;

        ListItem *root = (ListItem *)(&l.mRoot);

        root->next = root;
        root->prev = root;
        return *this;
    }
    ListTable(const ListTable &l)
    {
        *this = l;
    }
protected:

    void merge(ListNode *result, ListNode *left, ListNode *right)
    {
        for(ListNode *tmpR = right->next, *nextR = tmpR->next,
            *tmpL = left->next, *nextL = tmpL->next;
            tmpR != right && tmpL != left; )
        {
            if (static_cast<ListItem *>(tmpR)->_M_data < static_cast<ListItem *>(tmpL)->_M_data)
            {
                tmpL->del();
                result->addFirst(tmpL);
                tmpL  = nextL;
                nextL = nextL->next;
            } else
            {
                tmpR->del();
                result->addFirst(tmpR);
                tmpR = nextR;
                nextR = nextR->next;
            }
        }

        // 加到末尾
        if (!right->isEmpty())
        {
            for(ListNode *tmp = right->next, *next = tmp->next;
                tmp != right;
                tmp = next, next = next->next)
            {
                tmp->del();
                result->addFirst(tmp);
            }
        }

        if (!left->isEmpty())
        {
            for(ListNode *tmp = left->next, *next = tmp->next;
                tmp != left;
                tmp = next, next = next->next)
            {
                tmp->del();
                result->addFirst(tmp);
            }
        }
    }

    void mergeSort(ListNode *root)
    {
        // Do nothing if the list has length 0 or 1.
        if (root->next != root
                && root->next->next != root)
        {
            ListNode *first, *last;
            for (first = root->next, last = root->prev;
                 first->next != last && first != last;
                 first = first->next, last = last->prev);

            if (first == last) first = first->prev;
            // first和last指针已经相邻了

            ListNode rootR = *root, rootL = *root;
            // 把root列表平均拆成两个列表
            rootR.prev = first;
            rootR.next->prev = &rootR;

            rootL.next = last;
            rootL.prev->next = &rootL;

            first->next = &rootR;
            last->prev  = &rootL;

            // 清空root列表
            root->next = root;
            root->prev = root;

            mergeSort(&rootR);
            mergeSort(&rootL);

            merge(root, &rootL, &rootR);
        }
    }

private:
    ListItem mRoot;
};

#endif // LIST_TABLE_H
